The present invention relates generally to computer networks, and more particularly, to processing packets within a network.
A network is typically a data communication system which links two or more computers and peripheral devices to allow a user on a computer to access resources and exchange messages with users on other computers. Internetworking is the process of establishing and maintaining communications between and transferring data among multiple local networks in a distributed network system. The network allows users to share resources on their own systems with other network users and to access information on centrally located systems or on systems which are located at remote offices.
A network system typically includes a plurality of routing domains which are each collections of networks under a common administration which share a common routing strategy. Each routing domain includes one or more local networks which are attached to one or more routers. The local network in a routing domain may be a local area network (LAN), metropolitan area network (MAN), or wide area network (WAN), for example. The system includes source and destination nodes (end systems) which are typically computers (e.g., workstations and servers) but may be any type of device which includes a network interface card (NIC).
The routers within the routing domain manage communications among local networks within their domain and communicate with each other using an intradomain routing protocol. The routers transfer information to and from the end systems and among themselves along communication links in formatted packets. When an originating end system wants to transmit information to a destination end system, it generates a packet header in an appropriate format which includes the address of the destination end system, and then fills the remainder of the packet with the information to be transmitted. When a router receives a data packet, it reads the packet's destination address from the packet header and then transmits the packet on the link leading most directly to the packet's destination. Along the path from source to destination, the packet may be transmitted over several links and pass through several routers.
Internet Protocol (IP) is a standard that defines the manner in which the network layers of two hosts interact. These hosts may be on the same network or reside on physically distinct heterogeneous networks. IPv6 (Internet Protocol version 6) is the latest version of the protocol. IPv6 is the “next generation” protocol designed by the IETF to replace the current version Internet Protocol, IP Version 4 (“IPv4”). Most of today's Internet uses IPv4, which is now nearly twenty years old. IPv4 has been resilient in spite of its age, but it is beginning to have problems. Most importantly, there is a growing shortage of IPv4 addresses, which are needed by all new machines added to the Internet. Global Internet routing based on the 32-bit addresses of IPv4 is becoming increasingly strained. IPv4 addresses also do not provide enough flexibility to construct efficient hierarchies which can be aggregated. The new IP was created to deal with the large growth of the Internet. IPv6 fixes a number of problems in IPv4, such as the limited number of available IPv4 addresses. It also adds many improvements to IPv4 in areas such as routing and network auto configuration. IPv6 is expected to gradually replace IPv4, with the two coexisting for a number of years during a transition period. In order for routers to support IPv6, the problem of efficient forwarding of IPv6 packets needs to be addressed along with efficient updates of routing data structure used for forwarding packets.
Various methods have been proposed to implement IPv6 forwarding. A simple approach is to cache adjacency information for an earlier IPv6 destination. The performance improvement expected from this approach is small since each prefix may cover many destinations. Another option is netflow based acceleration. A drawback to this approach is that performance gain is limited, especially when average packets per flow is small. Also, it is not very scaleable since more flow entries will be needed for the same destination address. The current state of art for IPv4 lookup uses mtrie. Different variations of the mtrie-based approaches have been proposed for generic lookups. When applied to IPv6, these approaches either require memory larger than usually available or require many memory accesses which makes high performance implementation difficult to achieve.